package org.example.oneQuestionPerDay;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 2864. 最大二进制奇数

 * 提示
 * 给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。
 * 你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。
 * 以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。
 * 注意 返回的结果字符串 可以 含前导零。
 *
 * 示例 1：
 *
 * 输入：s = "010"
 * 输出："001"
 * 解释：因为字符串 s 中仅有一个 '1' ，其必须出现在最后一位上。所以答案是 "001" 。
 * 示例 2：
 *
 * 输入：s = "0101"
 * 输出："1001"
 * 解释：其中一个 '1' 必须出现在最后一位上。而由剩下的数字可以生产的最大数字是 "100" 。所以答案是 "1001" 。
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 100
 * s 仅由 '0' 和 '1' 组成
 * s 中至少包含一个 '1'
 * @author: daiziru
 * @createDate: 2024/3/13 14:17
 */
public class P2864 {
    public static void main(String[] args) {


        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        System.out.println("输入字符串：" + s);
        String  result= sortMethod(s);
        System.out.println("排序法:" + result);
        String result1 = doublePointer(s);
        System.out.println("双指正算法:" + result1);


    }

    /**
     * 双指针算法,假设存在字符串；0100101,首先，需要使用双指针算法，
     * 1、确保返回是奇数 ：先从字符串右边开始操作，找到右边第一个1，也就是最高位的1，然后把这个1所在的位置变为0，字符串最后一个位置变为1，确保返回的字符串是奇数
     * 2、把剩下的1全部放到左边，保证最大： 当左指针小于右指针， 循环查找左边第一个0，和右边第一个1，然后把两个位置的0和1交换，确保1来到左边，保证返回的数值是最大的二进制数
     * @param s 输入的字符串
     * @return
     */
    private static String doublePointer(String s) {
        char[] charArray = s.toCharArray();
        //定义指针
        int length = charArray.length;
        int left = 0, right = length - 2;
        //1、末尾置为1，确保返回的是奇数
        if(charArray[length - 1] == '0') {
            //寻找左边第一个1，也就是最高位的1
            while(right >= 0  && charArray[right] == '0') right--;
            //找到的1，换到字符串最后一位
            charArray[length - 1] = '1';
            charArray[right] = '0';
            right--;
        }


        //2、遍历，把所有的1换到左边
        while(left < right) {
            //寻找第一个0
            while(left < right && charArray[left] == '1') left++;
            //寻找剩下1中的最高位的1，上一步排序在最后的1已不再范围内
            while(left < right && charArray[right] == '0') right--;
            if(left < right) {
                charArray[left] = '1';
                charArray[right] = '0';
                left++;
                right--;
            }
        }
        return String.valueOf(charArray);

    }

    /**
     * 排序方法
     * @param s
     * @return
     */

    private static String sortMethod(String s) {
        char[] str = s.toCharArray();
        //默认是升序排序，0在前面，1在后面
        Arrays.sort(str);
        StringBuilder sb = new StringBuilder();
        for(int i = str.length - 2; i >= 0; i--) {
            sb.append(String.valueOf(str[i]));
        }
        sb.append("1");
        System.out.println(sb.toString());
        return sb.toString();
    }
}


